//你可以选择使用单链表或者双链表，设计并实现自己的链表。 
//
// 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。 
//
// 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 
//
// 实现 MyLinkedList 类： 
//
// 
// MyLinkedList() 初始化 MyLinkedList 对象。 
// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。 
// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 
// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 
// void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 
//index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。 
// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。 
// 
//
// 
//
// 示例： 
//
// 
//输入
//["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", 
//"deleteAtIndex", "get"]
//[[], [1], [3], [1, 2], [1], [1], [1]]
//输出
//[null, null, null, null, 2, null, 3]
//
//解释
//MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.addAtHead(1);
//myLinkedList.addAtTail(3);
//myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
//myLinkedList.get(1);              // 返回 2
//myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
//myLinkedList.get(1);              // 返回 3
// 
//
// 
//
// 提示： 
//
// 
// 0 <= index, val <= 1000 
// 请不要使用内置的 LinkedList 库。 
// 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 
// 
//
// Related Topics 设计 链表 👍 961 👎 0


package leetcode.editor.cn;

/**
 * 设计链表
 *
 * @author CodeTheory
 * @date 2023-11-06 15:47:28
 */
public class P707_DesignLinkedList {
    public static void main(String[] args) {
//	 	 Solution solution = new P707_DesignLinkedList().new Solution();
        MyLinkedList myLinkedList = new MyLinkedList();
//        System.out.println(myLinkedList.get(1));
//        myLinkedList.addAtIndex(0,0);
//        System.out.println(myLinkedList);
//        myLinkedList.addAtIndex(1,1);
//        myLinkedList.addAtIndex(0,1);
//        myLinkedList.addAtIndex(3,3);
//        System.out.println(myLinkedList);

//         myLinkedList.addAtHead(1);
//         System.out.println(myLinkedList);
//         myLinkedList.addAtTail(3);
//         System.out.println(myLinkedList);
//         myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
//         System.out.println(myLinkedList);
//         myLinkedList.get(1); // 返回 2
//         System.out.println(myLinkedList);
//         myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
//         System.out.println(myLinkedList);
//         myLinkedList.get(1); // 返回 3
//         System.out.println(myLinkedList);
//
//         myLinkedList.addAtHead(1);
//         System.out.println(myLinkedList);
//         myLinkedList.deleteAtIndex(0);
//         System.out.println("giao");
//         System.out.println(myLinkedList);


         myLinkedList.addAtTail(1);System.out.println(myLinkedList);
         myLinkedList.addAtTail(3);System.out.println(myLinkedList);
         myLinkedList.addAtIndex(1, 2);System.out.println(myLinkedList);
         System.out.println(myLinkedList.get(1));
         myLinkedList.deleteAtIndex(1);System.out.println(myLinkedList);
         System.out.println(myLinkedList.get(2));

    }


//leetcode submit region begin(Prohibit modification and deletion)

    static class MyLinkedList {
        private int size;
        private ListNode head;
        private ListNode tail;


        // 使用虚拟头尾节点
        public MyLinkedList() {
            head = new ListNode(null, 0, null);
            tail = new ListNode(head, 0, null);
            head.next = tail;
        }

        public ListNode getNode(int index) {
            // 边界检查 范围 [0, size - 1]
            if (index < 0 || index >= size) {
                return null;
            }
            ListNode curr;
            // 如果index 不到 size的一半
            if (index < (size >> 1)) {
                curr = head;
                for (int i = 0; i <= index; i++) {
                    curr = curr.next;
                }
            } else {
                curr = tail;
                for (int i = index; i < size; i++) {
                    curr = curr.prev;
                }
            }
            return curr;
        }

        public int get(int index) {
            ListNode node = getNode(index);
            return node == null ? -1 : node.val;
        }

        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        public void addAtIndex(int index, int val) {
            // 边界检查 [0, size]
            ListNode curr;
            ListNode prev;
            ListNode newNode;
            if (index == size) {
                curr = tail;
            } else {
                curr = getNode(index);
                if (curr == null) return;
            }
            prev = curr.prev;
            newNode = new ListNode(prev, val, curr);
            prev.next = newNode;
            curr.prev = newNode;
            size++;
        }

        public void deleteAtIndex(int index) {

            ListNode curr = getNode(index);
            if (curr == null) {
                return;
            }
            ListNode prev = curr.prev;
            curr.next.prev = prev;
            prev.next = curr.next;
            size--;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode curt = head.next;
            while (curt != tail) {
                sb.append(curt.val).append("->");
                curt = curt.next;
            }
            return sb.toString();
        }

        static class ListNode {
            int val;
            ListNode prev;
            ListNode next;

            public ListNode(ListNode prev, int val, ListNode next) {
                this.prev = prev;
                this.val = val;
                this.next = next;
            }
        }
    }
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
//leetcode submit region end(Prohibit modification and deletion)

// 单向链表
//static class  MyLinkedList {
//    private int size;
//    private Node head;
//
//    static class Node {
//        int val;
//        Node next;
//
//        public Node(int val, Node next) {
//            this.val = val;
//            this.next = next;
//        }
//    }
//
//    public MyLinkedList() {
//
//    }
//
//    public int get(int index) {
//        // 边界检查 范围 [0, size - 1]
//        if (index < 0 || index >= size ) {
//            return -1;
//        }
//        Node cur = head;
//        for (int i = 0; i < index; i++) {
//            cur = cur.next;
//        }
//        return cur.val;
//    }
//
//    public void addAtHead(int val) {
//        head = head == null ? new Node(val, null) : new Node(val, head);
//        size++;
//    }
//
//    public void addAtTail(int val) {
//        if (head == null) {
//            addAtHead(val);
//        } else {
//            Node cur = head;
//            while (cur.next != null) {
//                cur = cur.next;
//            }
//            cur.next = new Node(val, null);
//            size++;
//        }
//    }
//
//    public void addAtIndex(int index, int val) {
//        // 边界检查 [0, size]
//        if (index < 0 || size < index) {
//            return;
//        }
//
//        if (index == 0) {
//            addAtHead(val);
//        } else {
//            Node curt = head;
//            // 找到要插入的前一个位置
//            for (int i = 0; i < index - 1; i++) {
//                curt = curt.next;
//            }
//            curt.next = new Node(val, curt.next);
//            size++;
//        }
//
//    }
//
//    public void deleteAtIndex(int index) {
//        // 边界检查 范围 [0, size - 1]
//        if (index < 0 || index > size - 1 ) {
//            return;
//        }
//        if (index == 0) {
//            head = head.next;
//        } else {
//            // 找到删除元素的前一个节点
//            Node curt = head;
//            for (int i = 0; i < index - 1; i++) {
//                curt = curt.next;
//            }
//            curt.next = curt.next.next;
//        }
//        size--;
//    }
//
//    @Override
//    public String toString() {
//        StringBuilder sb = new StringBuilder();
//        Node curt = head;
//        while (curt != null) {
//            sb.append(curt.val).append("->");
//            curt = curt.next;
//        }
//        return sb.toString();
//    }
//}
}